package pers.tz.题目.leetcode.链表;

import pers.tz.common.ListNode;
import pers.tz.common.ListUtils;

/**
 * @author irony
 * @date 2024-03-16
 */
public class leetcode_0328_奇偶链表 {
//给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。
//
// 第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。
//
// 请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。
//
// 你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。
//
// 示例 1:
//输入: head = [1,2,3,4,5]
//输出:[1,3,5,2,4]
//
// 示例 2:
//输入: head = [2,1,3,5,6,4,7]
//输出: [2,3,6,7,1,5,4]
//
// 提示:
// n == 链表中的节点数
// 0 <= n <= 10⁴
// -10⁶ <= Node.val <= 10⁶

    public static void main(String[] args) {
        ListNode listNode = ListUtils.generateList(10, 1, 15);
        ListUtils.printList(listNode);

        ListNode listNode1 = oddEvenList(oddEvenList(listNode));
        ListUtils.printList(listNode1);
    }

    public static ListNode oddEvenList(ListNode head) {
        int index = 1;
        ListNode oddHead = null; // 奇数链表
        ListNode evenHead = null; // 偶数链表
        ListNode oddCur = null;
        ListNode evenCur = null;
        ListNode next = null;

        while (head != null) {
            next = head.next;
            head.next = null;

            if (index % 2 != 0) { // 奇数
                if (oddHead == null) {
                    oddHead = head;
                }

                if (oddCur != null) {
                    oddCur.next = head;
                }

                oddCur = head;
            } else { // 偶数
                if (evenHead == null) {
                    evenHead = head;
                }

                if (evenCur != null) {
                    evenCur.next = head;
                }

                evenCur = head;
            }

            index++;
            head = next;
        }

        if (oddCur != null) {
            oddCur.next = evenHead;
        }

        return oddHead;
    }

}
